#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
#include "implement.h"

int main(int argc, char *argv[])
{
  if(argc > 2) {
    printf("Too many argument.\n");
    printf("Input format:\n");
    printf("./BMA <sequence_file>\n");
    exit(0);
  }
  FILE *fp;//file pointer
  if(argc == 1) {//argv[1]
    if((fp = fopen("sequence.txt","r"))!=NULL) {
      printf("Open sequence.txt by default.\n");
    }
    else {
      printf("Can't open sequence.txt.\n");
    }
  }
  else if((fp = fopen(argv[1],"r"))== NULL) {
      printf("Can't open %s\n",argv[1]);
      exit(0);
  }

  uint64_t N,n;
  //a(N-1) = (a0,a1,...,aN-1)
  fscanf(fp,"%lu",&N);
  printf("N=%lu\n",N);
  int *seq=(int*)malloc(sizeof(int)*N);

  for (n = 0; n < N; ++n) {
    fscanf(fp,"%d",seq+n);
  }
  printf("a(%ld)=(",N-1);
  for (n = 0; n < N; ++n) {
    printf("%d",seq[n]);
  }
  printf(")\n");

  uint64_t e;
  bool iszero=1;
  for (n = 0; n < N; ++n) {
    if(seq[n]==1) {e=n;iszero=0;break;}
  }
  if(iszero) {
    printf("f%ld(x)=1\n",N-1);
    return 0;
  }
  printf("e=%ld (The minimum non-negative integer of a[e]=1 is satisfied)\n",e);

  uint64_t *f=(uint64_t*)malloc(sizeof(uint64_t)*N);
  uint8_t *l=(uint8_t*)malloc(sizeof(uint8_t)*N);
  uint8_t *d=(uint8_t*)malloc(sizeof(uint8_t)*N);
  f[-1]=1;
  l[-1]=0;
  //initialize
  for (n = 0; n < e; ++n) {
    f[n]=1;
    l[n]=0;
  }
  f[e]=(1<<(e+1))+1;
  l[e]=e+1;
  printf("f%ld(x)=",e);
  dtopoly(f[e]);
  printf("; l%ld=%ld\n",e,e+1);


  printf("|a(%2ld)|   n  | dn | ln  |LFSR(fn)\n",N-1);

  //loop
  bool flag=1;
  uint64_t m=1,k;
  for (n = e+1; n < N; ++n) {
    d[n]=0;
    for (int i = 0; i <= l[n-1]; i++) {
      //printf("%df=%ld,a[%ld]=%d\n",i,f[n-1]>>i&1,n-l[n-1]+i,seq[n-l[n-1]+i]);
      d[n] = d[n] ^ (( (f[n-1]>>i) & 1) * seq[n-l[n-1]+i]);
    }
    //printf("d[n]=%d\n",d[n]);
    if(d[n]==0) {f[n]=f[n-1];l[n]=l[n-1];}
    else {
      for (int j = n-2; j >= 0; --j) {
        m=1;
        if(l[j]<l[n-1]) {m=j+1;flag=0;break;}
      }
      if(flag) {m=0;flag=1;}
      //printf("m=%ld,m-l=%ld\n",m,m-l[m-1]);
      //printf("n=%ld,n-l=%ld\n",n,n-l[n-1]);
      if(m-l[m-1]>=(n-l[n-1])) {
        k=m-l[m-1]-(n-l[n-1]);
        //printf("k=%ld\n",k);
        f[n]=f[n-1]^(f[m-1]<<k);
        l[n]=l[n-1];
      }
      else {
        k=n-l[n-1]-(m-l[m-1]);
        //printf("k=%ld\n",k);
        f[n]=(f[n-1]<<k)^f[m-1];
        l[n]=k+l[n-1];
      }
    }
    printf("|  %d  |  %2ld  | %2d | %2d  | ",seq[n],n,d[n],l[n]);
    dtopoly(f[n]);
    printf("\n");
  }
  if(2*l[N-1]<=N) {
    printf("Because of %d=2*%d= 2*l[N-1] <= N =%ld,\n",2*l[N-1],l[N-1],N);
    printf("f[%ld](x) = ",N-1);
    dtopoly(f[N-1]);
    printf(" is the only minimal polynomial of sequence a(%ld).\n",N-1);
  }
  else {
    printf("Because of %d=2*%d= 2*l[N-1] > N =%ld,\n",2*l[N-1],l[N-1],N);
    printf("The minimal polynomials are not unique.\n");
    printf("f[%ld](x) = ",N-1);
    dtopoly(f[N-1]);
    printf(" is one of the minimal polynomials of sequence a(%ld).\n",N-1);
  }

  if(fclose(fp) != 0)
    printf("Error in closing file %s\n", argv[1]);
  return 0;
}

